/*
    希尔排序,先按照step步长，排序，然后我
*/
#include<stdio.h>
const int numbers_size=8;
int numbers[]={49,38,65,97,76,13,27,49};
void swap(int* a,int* b){//交换原变量的值
    int temp=*a;
    (*a)=*b;
    (*b)=temp;
}
void show(int array[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}

/**
下面的代码是根据王道书写的，还有https://oi-wiki.org/basic/shell-sort/#%E5%AE%9E%E7%8E%B0  这个好像不太一样，还使用了swap
@param: array待排序数组
@param: n 数组元素个数
 */
void shellSort(int array[],int n){
    int i,j;
    int step=n/2; //步长，每次都不同，这里使用下面的while初始化步长，实际上可以简单粗暴的令h=n/2，n是元素个数
    for(step;step>=1;step/=2){ //控制步长，每次减半，最后步长为1
        for(i=step;i<n;i++){//这里i从step开始，是因为array[]中step之前的作为每组内插入排序的第一个元素，就不参与选择了
        //每组内，从前一个元素开始寻找插入的下标
            int key=array[i];//保存待插入的元素
            for(j=i-step;j>=0 && key<array[j];j-=step){//这里的加加减减都是以h为单位的
                array[j+step]=array[j];//后移
            }
            array[j+step]=key;
        }
        show(numbers,numbers_size);
    }
}


int main(void){
    shellSort(numbers,numbers_size);
    show(numbers,numbers_size);
}